/**
 * 2
 *  
 * @Author : Ruoyu Wang
 * @DateTime : 24-9-22 下午6:59
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    vector<long long> nums(n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &nums[i]);
    }
    long long maxValue[n + 1][n + 1];
    vector<long long> maxVec(n + 1, 0);
    for (int len = 1; len <= n; ++len) {
        long long maxTmp = -0x3f3f3f3f3f3f3f3f;
        for (int i = 0, j = i + len; j <= n; ++i, ++j) {
            if (len == 1) {
                maxValue[i][j] = nums[i];
            } else {
                maxValue[i][j] = maxValue[i][j - 1] + nums[j - 1];
            }
            maxTmp = max(maxTmp, maxValue[i][j]);
        }
        if (len > 0) {
            maxVec[len] = maxTmp;
        }
    }

    long long maxLR[n + 1][n + 1];
    for (int len = 1; len <= n; ++len) {
        for (int i = 1, j = i + len - 1; j <= n; ++i, ++j) {
            if (len == 1) {
                maxLR[i][j] = maxVec[i];
            } else {
                maxLR[i][j] = max(maxLR[i][j - 1], maxLR[i + 1][j]);
            }
        }
    }
    while (q--) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%lld\n", maxLR[l][r]);
    }
    return 0;
}